// #define print(...)
class Solution {
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
    vector<int> pathMap[n];
    for(auto&line:relation)
        pathMap[line[0]].push_back(line[1]);
    // dfs
    int cntWay = 0;
    function<void(int,int)> dfs = [&](int src, int steps){
        if(k == steps){
            if(n-1 == src) cntWay++;
            return;
        }
        for(auto&dst:pathMap[src]){
            print(steps, ":", src, "->", dst, "\n")
            dfs(dst, steps+1);
        }
    };
    dfs(0, 0);
    return cntWay;
}
};

// 动态规则解法
class SolutionDP {
public:
int numWays(int n, vector<vector<int>>& relation, int k) {
    vector<int> dpNew(n,0), dpPre(n,0); // 经过 i 步到达各点的方案数
    dpNew[0] = 1;
    for(int i=0; i<k; i++){
        swap(dpNew, dpPre);
        dpNew.assign(n,0);
        for(auto&r:relation)
            dpNew[r[1]] += dpPre[r[0]];
        print(i, "th: new=", dpNew, ", pre=", dpPre, "\n")
    }
    return dpNew[n-1];
}
};
